//给定字符串 s 和 t ，判断 s 是否为 t 的子序列。 
//
// 字符串的一个子序列是原始字符串删除一些（也可以不删除）字符而不改变剩余字符相对位置形成的新字符串。（例如，"ace"是"abcde"的一个子序列，而"ae
//c"不是）。 
//
// 进阶： 
//
// 如果有大量输入的 S，称作 S1, S2, ... , Sk 其中 k >= 10亿，你需要依次检查它们是否为 T 的子序列。在这种情况下，你会怎样改变代
//码？ 
//
// 致谢： 
//
// 特别感谢 @pbrother 添加此问题并且创建所有测试用例。 
//
// 
//
// 示例 1： 
//
// 
//输入：s = "abc", t = "ahbgdc"
//输出：true
// 
//
// 示例 2： 
//
// 
//输入：s = "axc", t = "ahbgdc"
//输出：false
// 
//
// 
//
// 提示： 
//
// 
// 0 <= s.length <= 100 
// 0 <= t.length <= 10^4 
// 两个字符串都只由小写字符组成。 
// 
// Related Topics 双指针 字符串 动态规划 
// 👍 548 👎 0

package com.cute.leetcode.editor.cn;
public class IsSubsequence {
    public static void main(String[] args) {
        Solution solution = new IsSubsequence().new Solution();
    }
    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        /**
         * 1.判断s是否为t的子序列（t可以删除字母），双指针一次遍历
         * 可以使用indexOf进行查找
         */
        public boolean isSubsequence(String s, String t) {
            int p1 = 0;
            int p2 = 0;
            while (p1<s.length() && p2<t.length()){
                if (s.charAt(p1)==t.charAt(p2))p1++;
                p2++;
            }
            /*int index = -1;
            for (char c : s.toCharArray()) {
                index = t.indexOf(c, index + 1);
                if (index == -1) {
                    return false;
                }
            }*/
            return p1 == s.length();
        }
        /**
         * 2.换一种思路：可以使用动态规划，写推导状态转移方程
         *  dp[i][j]为s的从头开始到i的子字符串是否为t从头开始到j的子字符串的子序列
         *  当char[i]==char[j]时，则字符i一定是j的子序列，如果0~i-1子字符串是0~j-1子字符串的子序列
         *      则dp[i][j]=true，所以dp[i][j] = dp[i-1][j-1]；
         *
         *  当char[i]!=char[i]时，即判断当前0~i子字符串是否是0~j-1的子字符串的子序列
         *      即dp[i][j] = dp[i][j - 1]。如ab，eabc，虽然s的最后一个字符和t中最后一个字符不相等
         *      但是因为ab是eab的子序列，所以ab也是eabc的子序列
         *  初始化的时候dp[0][j]都置为true，空串是任意字符串的子串，遍历时i从1开始更新dp数组
         */
        public boolean dp(String s, String t) {
            int sLen = s.length();
            int tLen = t.length();
            boolean[][] dp = new boolean[sLen+1][tLen+1];
            for (int i = 0; i < tLen; i++) dp[0][i] = true;
            for (int i = 1; i <= sLen; i++) {//这里是双重循环了
                for (int j = 1; j <= tLen; j++) {
                    if (s.charAt(i - 1) == t.charAt(j - 1)) {
                        dp[i][j] = dp[i - 1][j - 1];
                    } else {
                        dp[i][j] = dp[i][j - 1];
                    }
                }
            }
            return dp[sLen][tLen];
        }
        /**
         * 二刷的时候只想起来indexOf的方法，没想到双指针以及动态规划
         * 看完代码随想录的题解才知道这一系列的题目属于“编辑距离”
         * 使用dp进行求解，dp[i][j]保存的是s和t到达i-1和j-1时的最大相同长度
         */
        public boolean dp2(String s, String t) {
            int[][] dp = new int[s.length()+1][t.length()+1];
            for (int i = 1; i <= s.length(); i++) {
                for (int j = 1; j <= t.length(); j++) {
                    if (s.charAt(i-1) == t.charAt(j-1)) dp[i][j] = dp[i-1][j-1] + 1;
                    else dp[i][j] = dp[i][j-1];//如果当前一个匹配不上，那就只能是之前的值了
                }
            }
            return dp[s.length()][t.length()] == s.length();
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}